/*
 * @Author: szx
 * @Date: 2022-01-27 14:28:05
 * @LastEditTime: 2022-01-27 14:40:08
 * @Description:
 * @FilePath: \leetcode\600-699\647\647.js
 */
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
    const n = s.length;
    // 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
    const dp = new Array(n).fill(false).map(() => new Array(n).fill(false));
    let res = 0;
    for (let i = n-1; i >=0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
};
